/*
ID: khymill1
PROG: checker 
LANG: C++
*/
#include <string.h>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <fstream>
#include <set>
using namespace std;

//method 1
void getNqueens(int level, vector<int> &pos, int &ans, vector<int> &a, vector<int> &b, vector<int> &c, vector<int> cur, vector<vector<int> > &result)
{
    if (level == pos.size()) {
        ans++;
        result.push_back(cur);
        return;
    }

   for (int i = 0; i < pos.size(); i++) {
      if (a[i] || b[level+i] || c[level-i+pos.size()-1]) continue;
      a[i] = 1;
      b[level+i] = 1;
      c[level-i+pos.size()-1] = 1;
      pos[level] = i;
      cur.push_back(i+1);
      getNqueens(level+1, pos, ans, a, b, c, cur, result);
      cur.pop_back();
      a[i] = 0;
      b[level+i] = 0;
      c[level-i+pos.size()-1] = 0;
   }
}

int main()
{
    ifstream fin("checker.in");
    ofstream fout("checker.out");
    int n;
    fin >> n;
    int ans = 0;                        
    vector<vector<int> > result;
    vector<int> cur;
    vector<int> pos(n,0);
    vector<int> a(n, 0);
    vector<int> b(2*n-1, 0);
    vector<int> c(2*n-1, 0);
    getNqueens(0, pos, ans, a, b, c, cur, result); 
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < result[i].size(); j++) 
            fout << result[i][j] << " " ; 
        fout << endl;
    }
    fout << ans << endl;
    return 0;
}                                          
